package 力扣算法练习.main1.part1;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class day9 {
    public static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
    /*
    给你链表的头节点 head ，每k个节点一组进行翻转，请你返回修改后的链表。
    k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是k的整数倍，
    那么请将最后剩余的节点保持原有顺序。
    https://leetcode.cn/problems/reverse-nodes-in-k-group
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        //用栈存入k个节点然后再弹出连接
        Stack<ListNode> temp=new Stack<>();
        ListNode result=new ListNode(),cur=result,htemp=head;
        int count=0;
        while(htemp!=null){
            temp.push(htemp);
            count++;
            htemp=htemp.next;
            if (count==k){
                //已经存了k个节点了将其反转
                while(!temp.isEmpty()){
                    cur.next=temp.pop();
                    cur=cur.next;
                    cur.next=null;//防止形成循环链表
                }
                count=0;
            }
        }
        //如果栈不为空就把栈的节点弹出后再连接栈底部元素
        while (!temp.isEmpty()){
            htemp=temp.pop();
            if (temp.isEmpty()){
                cur.next=htemp;
            }
        }
        return result.next;
    }


    /*
    给你两个字符串haystack 和 needle ，请你在 haystack 字符串中找出 needle
    字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
    https://leetcode.cn/problems/implement-strstr
     */
    public int strStr(String haystack, String needle) {
        if (needle.length()==0)return 0;
        //遍历第一个字符串出现字符相同的情况就到循环中比对剩余的字符
        int index1,count=0;
        for (int i = 0; i <haystack.length() ; i++) {
            index1=i;
            if (haystack.charAt(i)==needle.charAt(0)){
                int j = 0;
                for (; j < needle.length(); j++) {
                    if (needle.charAt(j)!=haystack.charAt(index1++))break;
                    count++;
                    if (index1==haystack.length())break;
                }
                if (count==needle.length())return i;
            }
            count=0;
        }
        return -1;
    }


    /*
    给定两个整数，被除数dividend和除数divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
    返回被除数dividend除以除数divisor得到的商。
    整数除法的结果应当截去（truncate）其小数部分
    https://leetcode.cn/problems/divide-two-integers
     */
    //错误代码
/*    public int divide(int dividend, int divisor) {
        //拿被除数一直减去除数直到结果小于除数返回减了几次(先统一为正数)
        long d1=dividend,d2=divisor;
        boolean flag1=false,flag2=false;
        if (d1<0){
            flag1=true;
            d1=-d1;
        }
        if (d2<0){
            flag2=true;
            d2=-d2;
        }
        long count=0;
        while(d1>=d2){
            d1-=d2;
            count++;
        }
        if (divisor==-1&&dividend==Integer.MIN_VALUE)count--;
        if (flag1)count=-count;
        if (flag2)count=-count;
        return (int)count;
    }*/
    //官方解
    class Solution {
        public int divide(int dividend, int divisor) {
            // 考虑被除数为最小值的情况
            if (dividend == Integer.MIN_VALUE) {
                if (divisor == 1) {
                    return Integer.MIN_VALUE;
                }
                if (divisor == -1) {
                    return Integer.MAX_VALUE;
                }
            }
            // 考虑除数为最小值的情况
            if (divisor == Integer.MIN_VALUE) {
                return dividend == Integer.MIN_VALUE ? 1 : 0;
            }
            // 考虑被除数为 0 的情况
            if (dividend == 0) {
                return 0;
            }

            // 一般情况，使用类二分查找
            // 将所有的正数取相反数，这样就只需要考虑一种情况
            boolean rev = false;
            if (dividend > 0) {
                dividend = -dividend;
                rev = !rev;
            }
            if (divisor > 0) {
                divisor = -divisor;
                rev = !rev;
            }

            List<Integer> candidates = new ArrayList<Integer>();
            candidates.add(divisor);
            int index = 0;
            // 注意溢出
            while (candidates.get(index) >= dividend - candidates.get(index)) {
                candidates.add(candidates.get(index) + candidates.get(index));
                ++index;
            }
            int ans = 0;
            for (int i = candidates.size() - 1; i >= 0; --i) {
                if (candidates.get(i) >= dividend) {
                    ans += 1 << i;
                    dividend -= candidates.get(i);
                }
            }

            return rev ? -ans : ans;
        }
    }

}
